//
//  Permute.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/6/28.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  46. 全排列

import UIKit

/*
 46. 全排列
 给定一个 没有重复 数字的序列，返回其所有可能的全排列。

 示例:

 输入: [1,2,3]
 输出:
 [
   [1,2,3],
   [1,3,2],
   [2,1,3],
   [2,3,1],
   [3,1,2],
   [3,2,1]
 ]
 */

class Permute: NSObject {
    
    var resultArr:[[Int]] = []
    
    func permute(_ nums: [Int]) -> [[Int]] {
        
        let boolArr = Array.init(repeating: false, count: nums.count)
        
        self.dfs(0, [], nums, boolArr)

        return resultArr
    }
    
    func dfs(_ startIndex:Int, _ tmpArr:[Int], _ sourceArr:[Int], _ flagArr:[Bool]){
        
        var arr = tmpArr
        var flagArr = flagArr
        
        if arr.count == sourceArr.count {
            resultArr.append(arr)
            return
        }
        
        for index in 0 ..< sourceArr.count {
            if flagArr[index] == true {
                continue
            }
            flagArr[index] = true
            arr.append(sourceArr[index])
            
            self.dfs(startIndex + 1, arr, sourceArr, flagArr)
            
            arr.removeLast()
            flagArr[index] = false
        }
        
    }
}
